package 第四周;

/*
 * @author  YxinMiracle
 * @date  2022-05-01 10:06
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 面试题后继者 {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return getNext(root,p.val);
    }

    private TreeNode getNext(TreeNode root, int val) {
        TreeNode ans = null;
        TreeNode curr = root;
        while (curr != null){
            if (curr.val == val){
                // 如果找到了点，那么就在右子树中一路向左走
                curr = curr.right;
                if (curr.left != null){
                    while (curr.left != null) ans = curr.left;
                }
            }

            if (val > root.val){
                curr = curr.right;
            }else {
                // 当前的值比当前正在对比的节点小
                // 走过的路中一定有一个点是答案
                // ans == null 说明还没有答案
                // 或者说当前的节点比答案小，那么就更新答案
                if (ans == null || ans.val < curr.val) ans = curr;
                curr = curr.left;
            }
        }
        return ans;
    }
}
